package 排序.归并排序.算法第四版实现方式;

/**
 * 将两个有序的数组归并为一个更大的有序的数组
 */
public abstract class 归并排序<T extends Comparable<T>> extends Sort<T> {

    protected T[] aux;

    protected void merge(T[] nums, int l, int m, int h) {

        int i = l, j = m + 1;

        for (int k = l; k <= h; k++) {
            aux[k] = nums[k]; // 将数据复制到辅助数组
        }

        for (int k = l; k <= h; k++) {
            if (i > m) {
                // 左半边用尽，取右半边的元素
                nums[k] = aux[j++];
            } else if (j > h) {
                // 右半边用尽，取左半边的元素
                nums[k] = aux[i++];
            } else if (aux[i].compareTo(nums[j]) <= 0) {
                // 右半边的当前元素小于左半边的当前元素，取右半边元素
                nums[k] = aux[i++]; // 先进行这一步，保证稳定性
            } else {
                // 右半边的当前元素大于等于左半边的当前元素，取左半边元素
                nums[k] = aux[j++];
            }
        }
    }
}